package CyclicLinkedList;

public class SinglyCircularLinkedList {
    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;
    private int length;

    public SinglyCircularLinkedList() {
        head = null;
        length = 0;
    }

    // 头插法
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            newNode.next = head;
            head = newNode;
            temp.next = head;
        }
        length++;
    }

    // 尾插法
    public void insertAtTail(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
        length++;
    }

    // 删除节点
    public boolean deleteNode(int data) {
        if (head == null) return false;

        Node current = head, prev = null;

        do {
            if (current.data == data) {
                if (current == head) {
                    // 如果是头节点
                    Node last = head;
                    while (last.next != head) {
                        last = last.next;
                    }
                    head = current.next;
                    last.next = head;
                    if (current == current.next) {
                        head = null; // 只有一个节点的情况
                    }
                } else {
                    prev.next = current.next;
                }
                length--;
                return true;
            }
            prev = current;
            current = current.next;
        } while (current != head);

        return false;
    }

    // 反转链表
    public void reverse() {
        if (head == null || head.next == head) return;

        Node prev = null, current = head, next = null;
        Node lastNode = head;

        // 找到最后一个节点
        while (lastNode.next != head) {
            lastNode = lastNode.next;
        }

        do {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        } while (current != head);

        head = prev;
        lastNode.next = head;
    }

    // 打印链表
    public void display() {
        if (head == null) {
            System.out.println("链表为空");
            return;
        }

        Node temp = head;
        do {
            System.out.print(temp.data);
            if (temp.next != head) {
                System.out.print(", ");
            }
            temp = temp.next;
        } while (temp != head);
        System.out.println();
    }

    public int getLength() {
        return length;
    }
}